Switching systems (also referred to as “switching networks”) route data through and among data communications networks. Switching systems typically comprise a plurality of switches and clusters of switches (“nodes”) that provide data communications paths among elements of data communications networks.
The “topology” of a switching network refers to the particular arrangement and interconnections (both physical and logical) of the nodes of a switching network. Knowledge of the topology of a switching network is used to compute communications paths through the network.
For switching systems that comprise a small number of individual switches, the topology is fairly straightforward and can be described by identifying the individual nodes in the system and the communications links between them. For larger and more complex networks, however, the amount of data needed to identify all links between all nodes of the network can be quite extensive.
A number of approaches have been proposed to reduce the amount of information needed to describe the topology of complex switching networks. One approach involves grouping physical nodes into groups (“peer groups”) that are viewed as individual logical nodes (“logical group nodes”) having characteristics that comprise an aggregation of the characteristics of the individual nodes within the group. Such logical group nodes may be further grouped with other physical and/or logical nodes to form successively higher level peer groups, creating a hierarchy of peer groups and logical group nodes.
One example of a network that allows physical nodes to be grouped into levels of logical groups of nodes is a “PNNI” network. PNNI, which stands for either “Private Network Node Interface” or “Private Network Network Interface,” is a routing and signaling protocol developed by the ATM Forum. The PNNI routing protocol is used to distribute topology information between switches and clusters of switches within a private ATM switching network. The PNNI signaling protocol is used to set up data connections within the PNNI network, via signaling call setup messages through the network.
A PNNI network is a network that utilizes the PNNI routing and signaling protocol. Within the PNNI routing protocol a Logical Group Node (LGN) is an abstract representation of a lower level Peer Group (PG) as a single point for the purposes of operating at one level of the PNNI routing hierarchy. Logical Group Nodes are created in a switching system via configuration and become operational dynamically as a result of the PNNI routing protocol behavior. Within the PNNI routing hierarchy a lowest level node is an abstraction representing a single instance of the PNNI routing protocol. Lowest level nodes are created in a switching system via configuration and are always operational. An LGN or a lowest level node is also known as a logical node or a node for the purpose of the present application. Other terms which will be used in this application are an entry border node which is a node at which a call setup message enters a peer group and an exit border node which is a node from which a call setup message leaves a peer group.
The PNNI routing protocol is used typically in ATM products to distribute information about changing network topology and network resources among a group of associated switches. Topology information is organized and distributed in a hierarchical fashion, or a flat single peer group, depending on the network topology. Hierarchy allows networks to scale their topologies to a very large number of nodes. The PNNI implementation provides the required support to exist and participate in the multilevel hierarchical network.
In a hierarchical network, nodes in the PNNI routing domain are grouped into peer groups. Nodes in the same peer group elect a peer group leader. The peer group leader is responsible for activating a logical group node (LGN) at the second level of hierarchy as well as existing as the logical node in the lowest level. The newly activated LGN exchanges PNNI routing information with other neighbor LGNs at the second level of hierarchy. The neighbor LGNs are other LGNs that other lower level PGLs instantiated from adjacent peer groups. In addition to exchanging information the LGN propagates information from higher levels down into the lower level peer group via the PGL that instantiated it. This is so that all nodes in the lower level peer group have the same information about the other LGNs in the higher level peer group where the activated LGN exists. From the hierarchical topology information gathered by a node, routing tables are created and used by the switches to route calls using the PNNI signaling protocol. PNNI networks and hierarchical groupings are described in co-pending U.S. application publication 20040085961 filed Nov. 1, 2002 entitled “Method for Advertising Reachable Address Information in a Network” the contents of which are incorporated herein by reference.
Routing tables are used by a node routing a call to create a Designated Transit List (DTL), which is a source route list to a destination node where a call is to be forwarded. A DTL is a list of PNNI nodes and port IDs that describe the path through a PNNI network on which a user call setup message is to proceed. In a hierarchical network, a stack of DTLs is used to represent the route to be taken at the different levels of hierarchy in the network. DTLs on the stack are added (pushed) by the DTL originator and entry border nodes and removed (popped) by exit border nodes along the route of the call, The DTL stack is sent in the setup message to set up the call using the PNNI signaling protocol.
In the present application reference is made to a crankback feature. The PNNI signaling protocol, as developed by the ATM Forum, supports crankback. In PNNI crankback a call, failing to set up at a certain node, is regressed to the node that last pushed DTLs onto the DTL stack which can be a DTL originator or entry border node. There is enough information in the crankback to indicate where the call was blocked. The information in the crankback provides the type of blocking (node, link, succeeding end of the link), and the location of the blocking (node Id for a node blocking type, or preceding and succeeding node Ids at both ends of a link for a link blocking type). According to the crankback procedures in the PNNI specification, an entry border node failing to route a call within its peer group, should crankback the call to the higher level with a “node blocked” or “link blocked” crankback message. Thus, an entry border node in the last peer group (i.e. an entry border node routing to a lowest level destination physical node), can generate a link blocked crankback message, having a null succeeding node Id (all zeros), at a higher level if the entry border node fails to route the call to the destination node. This would result in the blocking of the destination LGN, hence stopping further re-routing attempts from other routing-capable entry border nodes and/or the DTL originator towards the destination, even if other valid paths may exist. The problem manifests itself when there are multiple entry border nodes into the destination LGN's peer group for a call and the selected entry border node cannot find a route to the destination node even though one would have existed had the call chosen a different entry border node from which to enter the destination LGN's peer group. This situation typically occurs when a call selects a specific entry border node in the destination LGN's peer group, and there are no paths available from that entry border node (for example due to bandwidth shortage) to the actual physical destination node.
The limitation of the crankback provisions as set out in the PNNI protocol are illustrated in the following examples.
Referring to FIG. 1, a call is made from A.1 to C.3 following top-most level DTL (A-B-C). In peer group B, B.2 the exit border node forwards the call to C.1. Due to insufficient bandwidth on link C.1-C.3, entry border node C.1 must crankback the call. According to prior art PNNI crankback procedures, node C.1 generates a link blocked crankback at the second level (C, 0). This crankback is propagated in peer group B back to A.1, the DTL originator. A.1 finds that the destination peer group is blocked, and thus attempts no other route to the destination, although there is a direct link between A and C.
Referring to FIG. 2, a call is made from A.1 to C22 using top-most level DTL (A-C). In peer group C, entry border node C1 (physical node C11) fails to route the call due to insufficient bandwidth on link C11-C12. According to prior art PNNI crankback procedures, entry border node C1 (physical node C11), generates a link blocked crankback (C, 0), since it is in the last LGN in the call's DTL stack. When A.1, the DTL originator, receives this crankback, it interprets that the LGN C is blocked. Since LGN C is the destination LGN, no other routes can be attempted, although route A-B-C is a valid route
The above limitations in the PNNI crankback procedures as set out in the PNNI specification are addressed by the present application.